class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int ans = 0;
        int l = 1, r = n - 2, lmax = height[0], rmax = height[n - 1];
        while (l <= r)
        {
            if (lmax <= rmax)
            {
                ans += max(0, lmax - height[l]);
                lmax = max(height[l++], lmax);
            }

            if (lmax > rmax)
            {
                ans += max(0, rmax - height[r]);
                rmax = max(height[r--], rmax);
            }
        }
        return ans;
    }
};